package com.mccken.practice.top100.Top_1$20.top_9;

import java.util.HashMap;
import java.util.Map;

/**
 * 500.和为 K 的子数组
 * 我的思路： 滑动窗口计算  ——> 错误的。
 * <p>
 * 正确的思路是：前缀和+哈希表
 * <p>
 * 伪代码：
 * 遍历数组时候，构造前缀和、再跟着构造哈希表
 *
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-02 08:29
 **/
public class SubarraySum {

	public int subarraySum(int[] nums, int k) {
		if (nums.length == 1) {
			return nums[0] == k ? 1:0; 
		}
		

		// 前缀和-出现次数
		Map<Integer, Integer> map = new HashMap<>();
		// 结果
		int res = 0;
		int[] sums = new int[nums.length];
		for (int i = 0; i < nums.length; i++) {
			int pre_sum = 0;
			if (i > 0) {
				pre_sum = sums[i - 1];
			}
			sums[i] = pre_sum + nums[i];
			
			// 本身满足k
			if (sums[i] == k) {
				res++;
			}
		
			// 再从hash中获取差值的次数
			res += map.getOrDefault(sums[i]-k, 0);
			map.merge(sums[i], 1, Integer::sum);
		}
		return res;
	}

	public static void main(String[] args) {
		SubarraySum subarraySum = new SubarraySum();
//		System.out.println(subarraySum.subarraySum(new int[]{1,1,1}, 2));
//		System.out.println(subarraySum.subarraySum(new int[]{1,2,3}, 3));
//		System.out.println(subarraySum.subarraySum(new int[]{1}, 0));
		System.out.println(subarraySum.subarraySum(new int[]{-1,-1,1}, 0));
	}
}
